﻿//20.有效的括号
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//有效字符串需满足：
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。
class Solution {
public:
    bool isValid(string s)
    {
        stack<int> st;
        int i = 0;
        while (i < s.size())
        {

            if (s[i] == '}')
            {
                if ((!st.empty()) && st.top() == '{')
                {
                    st.pop();
                }
                else
                {
                    return false;
                }
            }
            else if (s[i] == ']')
            {
                if ((!st.empty()) && st.top() == '[')
                {
                    st.pop();
                }
                else
                {
                    return false;
                }
            }
            else if (s[i] == ')')
            {
                if ((!st.empty()) && st.top() == '(')
                {
                    st.pop();
                }
                else
                {
                    return false;
                }
            }
            else
            {
                st.push(s[i]);
            }
            i++;
        }
        if (st.empty())
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};